// 链表的一些操作
package main

import (
	"fmt"
)

// 单链表节点
type ListNode struct {
	next  *ListNode
	value interface{}
}

// 单链表
type LinkedList struct {
	head *ListNode
}

// 打印链表
func (this *LinkedList) Print() {
	cur := this.head.next
	format := ""
	for nil != cur {
		format += fmt.Sprintf("%+v", cur.value)
		cur = cur.next
		if nil != cur {
			format += "->"
		}
	}
	fmt.Println(format)
}

/*
单链表反转
时间复杂度：O(N)
*/
func (this *LinkedList) Reverse() {
	if nil == this.head || nil == this.head.next || nil == this.head.next.next {
		return
	}

	var pre *ListNode = nil
	cur := this.head.next
	for nil != cur {
		tmp := cur.next
		cur.next = pre
		pre = cur
		cur = tmp
	}

	this.head.next = pre
}

/*
判断单链表是否有环
*/
func (this *LinkedList) HasCycle() bool {
	if nil != this.head {
		slow := this.head
		fast := this.head
		for nil != fast && nil != fast.next {
			slow = slow.next
			fast = fast.next.next
			if slow == fast {
				return true
			}
		}
	}
	return false
}

/*
两个有序单链表合并
*/
func MergeSortedList(l1, l2 *LinkedList) *LinkedList {
	if nil == l1 || nil == l1.head || nil == l1.head.next {
		return l2
	}
	if nil == l2 || nil == l2.head || nil == l2.head.next {
		return l1
	}

	l := &LinkedList{head: &ListNode{}}
	cur := l.head
	curl1 := l1.head.next
	curl2 := l2.head.next
	for nil != curl1 && nil != curl2 {
		if curl1.value.(int) > curl2.value.(int) {
			cur.next = curl2
			curl2 = curl2.next
		} else {
			cur.next = curl1
			curl1 = curl1.next
		}
		cur = cur.next
	}

	if nil != curl1 {
		cur.next = curl1
	} else if nil != curl2 {
		cur.next = curl2
	}

	return l
}

/*
删除倒数第N个节点
*/
func (this *LinkedList) DeleteBottomN(n int) {
	if n <= 0 || nil == this.head || nil == this.head.next {
		return
	}

	fast := this.head
	for i := 1; i <= n && fast != nil; i++ {
		fast = fast.next
	}

	if nil == fast {
		return
	}

	slow := this.head
	for nil != fast.next {
		slow = slow.next
		fast = fast.next
	}
	slow.next = slow.next.next
}

/*
获取中间节点
*/
func (this *LinkedList) FindMiddleNode() *ListNode {
	if nil == this.head || nil == this.head.next {
		return nil
	}
	if nil == this.head.next.next {
		return this.head.next
	}

	slow, fast := this.head, this.head
	for nil != fast && nil != fast.next {
		slow = slow.next
		fast = fast.next.next
	}
	return slow
}

// 测试
var l *LinkedList

func init() {
	n5 := &ListNode{value: 5}
	n4 := &ListNode{value: 4, next: n5}
	n3 := &ListNode{value: 3, next: n4}
	n2 := &ListNode{value: 2, next: n3}
	n1 := &ListNode{value: 1, next: n2}
	l = &LinkedList{head: &ListNode{next: n1}}
}

// 测试:单链表反转
func reverse() {
	l.Print() //1->2->3->4->5
	l.Reverse()
	l.Print() //5->4->3->2->1
}

// 测试:判断单链表是否有环
func hasCycle() {
	fmt.Println(l.HasCycle())                                    //false
	l.head.next.next.next.next.next.next = l.head.next.next.next //加环
	fmt.Println(l.HasCycle())                                    //true
}

// 测试:两个有序单链表合并
func mergeSortedList() {
	n5 := &ListNode{value: 9}
	n4 := &ListNode{value: 7, next: n5}
	n3 := &ListNode{value: 5, next: n4}
	n2 := &ListNode{value: 3, next: n3}
	n1 := &ListNode{value: 1, next: n2}
	l1 := &LinkedList{head: &ListNode{next: n1}}

	n10 := &ListNode{value: 10}
	n9 := &ListNode{value: 8, next: n10}
	n8 := &ListNode{value: 6, next: n9}
	n7 := &ListNode{value: 4, next: n8}
	n6 := &ListNode{value: 2, next: n7}
	l2 := &LinkedList{head: &ListNode{next: n6}}

	MergeSortedList(l1, l2).Print() //1->2->3->4->5->6->7->8->9->10
}

// 测试:删除倒数第N个节点
func deleteBottomN() {
	l.Print()          //1->2->3->4->5
	l.DeleteBottomN(3) //删除倒数第3个节点
	l.Print()          //1->2->4->5
}

// 测试:获取中间节点
func findMiddleNode() {
	l.DeleteBottomN(1)              //删除倒数第1个节点
	l.DeleteBottomN(1)              //再次删除倒数第1个节点
	l.Print()                       //1->2->3
	fmt.Println(l.FindMiddleNode()) //&{0xc000010078 2}
}

func main() {
	//reverse()
	//hasCycle()
	//mergeSortedList()
	//deleteBottomN()
	findMiddleNode()
}
